
/*
记忆化搜索
连接：https://leetcode.cn/problems/unique-paths/description/
题目： 不同路径







  

   
    
*/
///记忆化搜索
class Solution {
public:
    int memo[101][101];
    int uniquePaths(int m, int n) {
        //记忆化搜索
        memset(memo,-1,sizeof(memo));
        return dfs(m,n);


    }
    int dfs(int i,int j)
    {
        if(memo[i][j]!=-1)
            return memo[i][j];
        if(i==0 || j==0)
            return 0;
        if(i==1 && j==1)
         {   
             memo[i][j] = 1;
             return 1;
         }
         memo[i][j] = dfs(i-1,j) + dfs(i,j-1);
        return memo[i][j];
    }
};
//动规
int uniquePaths(int m, int n) {
        //记忆化搜索
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        dp[1][1] = 1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==1 &&j==1)
                    continue;
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
        //动规

    }